#![allow(dead_code)]
use std::iter::FromIterator;

fn hanoi(n: usize) {
    hanoi_recurrence(n, "A", "C", "B");
}

fn hanoi_recurrence(n: usize, from: &str, to: &str, mid: &str) {
    if n == 0 {
        return;
    }

    hanoi_recurrence(n - 1, from, mid, to);
    println!("盘[{}]: {} -> {}", n, from, to);
    hanoi_recurrence(n - 1, mid, to, from);
}

pub fn test_hanoi() {
    hanoi(3);
}

pub fn print_all_sub_sequence(s: &str) {
    let mut ss: Vec<char> = s.to_string().chars().collect();
    sub_sequence(&mut ss, 0);
    println!("");
}

fn sub_sequence(s: &mut Vec<char>, idx: usize) {
    if idx == s.len() {
        let mut x = String::from_iter(s.iter());
        x.retain(|c| c != ' ');
        print!("{:?}, ", x);
        return;
    }

    sub_sequence(s, idx + 1);
    let tmp = s[idx];
    s[idx] = ' ';
    sub_sequence(s, idx + 1);
    s[idx] = tmp;
}

fn permutation(s: &mut Vec<char>, idx: usize, res: &mut Vec<String>) {
    if idx == s.len() {
        res.push(String::from_iter(s.iter()));
        return;
    }

    let mut visit = vec![false; 26];
    for j in idx..s.len() {
        if !visit[s[j] as usize - 'a' as usize] {
            visit[s[j] as usize - 'a' as usize] = true;
            s.swap(idx, j);
            permutation(s, idx + 1, res);
            s.swap(idx, j);
        }
    }
}

pub fn print_permutation(s: &str) {
    println!("字符串: {}的全排序为：", s);
    let mut res: Vec<String> = vec![];
    let mut s: Vec<char> = s.to_string().chars().collect();
    permutation(&mut s, 0, &mut res);
    println!("{:?}", res);
}

fn frist(card: &Vec<u32>, l: usize, r: usize) -> u32 {
    if l == r {
        return card[l];
    }

    std::cmp::max(
        frist(card, l, l) + second(card, l + 1, r),
        frist(card, r, r) + second(card, l, r - 1),
    )
}

fn second(card: &Vec<u32>, l: usize, r: usize) -> u32 {
    if l == r {
        return 0;
    }

    std::cmp::min(frist(card, l + 1, r), frist(card, l, r - 1))
}

pub fn play_card(card: Vec<u32>) {
    println!("纸牌：{:?}", card);
    println!(
        "获胜高分: {}",
        std::cmp::max(
            frist(&card, 0, card.len() - 1),
            second(&card, 0, card.len() - 1)
        )
    );
}

fn stack_bottom(stack: &mut Vec<i32>) -> i32 {
    let res = stack.pop().unwrap();
    if stack.is_empty() {
        return res;
    } else {
        let last = stack_bottom(stack);
        stack.push(res);
        return last;
    }
}

fn reverse_stack(stack: &mut Vec<i32>) {
    if stack.is_empty() {
        return;
    }
    let bottom = stack_bottom(stack);
    reverse_stack(stack);
    stack.push(bottom);
}

pub fn test_reverse_stack() {
    let mut stack = vec![1, 2, 3, 4, 5];
    println!("栈：{:?}", stack);
    reverse_stack(&mut stack);
    println!("反转：{:?}", stack);
}

// [0..i-1]如何转化已经做过决定
// [i..]有多少种转化结果
fn trans_methods(s: &Vec<char>, i: usize) -> i32 {
    let slen = s.len();
    if slen == i {
        return 1;
    }
    match s[i] {
        // 进入无效状态，虽然a[..i-1]转化有效，所以整体是0种
        '0' => return 0,
        '1' => {
            // s[i]独立转化，后续a[i+1..]有多少种
            let mut res = trans_methods(s, i + 1);
            // s[i]和s[i+1]组合，后续a[i+2..]有多少种
            if i + 1 < slen {
                res += trans_methods(s, i + 2);
            }
            return res;
        }
        '2' => {
            let mut res = trans_methods(s, i + 1);
            if i + 1 < slen && '0' <= s[i + 1] && s[i + 1] <= '6' {
                res += trans_methods(s, i + 2);
            }
            return res;
        }
        _ => {
            return trans_methods(s, i + 1);
        }
    }
}

pub fn test_trans_method() {
    let s = "1112".to_string().chars().collect();
    let ms = trans_methods(&s, 0);
    println!("ms: {}", ms);
}

fn max_value(
    weight: &mut Vec<i32>,
    values: &mut Vec<i32>,
    i: usize,
    alread_weight: i32,
    bag: i32,
) -> i32 {
    if alread_weight > bag {
        return 0;
    }
    // 没货了，要的货超过了货物数目
    if i == weight.len() {
        return 0;
    }
    std::cmp::max(
        // 不选第i件
        max_value(weight, values, i + 1, alread_weight, bag),
        // 选第i件
        values[i] + max_value(weight, values, i + 1, alread_weight + weight[i], bag),
    )
}
